{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Possible Full Binary Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #recursion #memoization #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #递归 #记忆化搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: allPossibleFBT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有可能的真二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你找出所有可能含 <code>n</code> 个节点的 <strong>真二叉树</strong> ，并以列表形式返回。答案中每棵树的每个节点都必须符合 <code>Node.val == 0</code> 。</p>\n",
    "\n",
    "<p>答案的每个元素都是一棵真二叉树的根节点。你可以按 <strong>任意顺序</strong> 返回最终的真二叉树列表<strong>。</strong></p>\n",
    "\n",
    "<p><strong>真二叉树</strong> 是一类二叉树，树中每个节点恰好有 <code>0</code> 或 <code>2</code> 个子节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/22/fivetrees.png\" style=\"width: 700px; height: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>[[0,0,0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-possible-full-binary-trees](https://leetcode.cn/problems/all-possible-full-binary-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-possible-full-binary-trees](https://leetcode.cn/problems/all-possible-full-binary-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def construct(n):\n",
    "            if n in memo:\n",
    "                return memo[n]\n",
    "            if n == 1:\n",
    "                return [TreeNode()]\n",
    "            ret = []\n",
    "            for left_nodes_count in range(1, n-1, 2):\n",
    "                for l in construct(left_nodes_count):\n",
    "                    for r in construct(n-1-left_nodes_count):\n",
    "                        ret.append(TreeNode(left=l, right=r))\n",
    "            memo[n] = ret\n",
    "            return ret\n",
    "        \n",
    "        memo = {}\n",
    "        return construct(n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = collections.defaultdict(list)\n",
    "    \n",
    "    def allPossibleFBT(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        \n",
    "        if N % 2 == 0:\n",
    "            return []\n",
    "        if N == 1:\n",
    "            return [TreeNode(0)]\n",
    "        if N in self.memo:\n",
    "            return self.memo[N]\n",
    "        res = []\n",
    "        for i in range(N):\n",
    "            j = N - 1 - i\n",
    "            left = self.allPossibleFBT(i)\n",
    "            right = self.allPossibleFBT(j)\n",
    "            for l in left:\n",
    "                for r in right:\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = l\n",
    "                    root.right = r\n",
    "                    res.append(root)\n",
    "        self.memo[N] = res\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    dp = [[TreeNode(0)]]\n",
    "\n",
    "    def allPossibleFBT(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if n % 2 == 0:\n",
    "            return []\n",
    "        dp = Solution.dp\n",
    "        for l in range(len(Solution.dp), n // 2 + 1):\n",
    "            new = []\n",
    "            for i in range(l):\n",
    "                for a, b in itertools.product(dp[i], dp[l - 1 - i]):\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = a\n",
    "                    root.right = b\n",
    "                    new.append(root)\n",
    "            dp.append(new)\n",
    "        return dp[n // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import functools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    @functools.lru_cache()\n",
    "    def allPossibleFBT(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if N % 2 == 0:\n",
    "            return []\n",
    "        if N == 1:\n",
    "            return [TreeNode(0)]\n",
    "        \n",
    "        for i in range(1, N-1, 2):\n",
    "            left = self.allPossibleFBT(i)\n",
    "            right = self.allPossibleFBT(N-1-i)\n",
    "            for l in left:\n",
    "                for r in right:\n",
    "                    p = TreeNode(0)\n",
    "                    p.left = l\n",
    "                    p.right = r\n",
    "                    res.append(p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        def dfs(num):\n",
    "            if num not in dicti:\n",
    "                if num < 2:\n",
    "                    return [[None], [TreeNode(0)]][num]\n",
    "                ans = []\n",
    "                for i in range(1, num, 2):\n",
    "                    for l in dfs(i):\n",
    "                        for r in dfs(num - 1 - i):\n",
    "                            root = TreeNode(0)\n",
    "                            root.left, root.right = l, r\n",
    "                            ans.append(root)\n",
    "                dicti[num] = ans\n",
    "            return dicti[num]\n",
    "        \n",
    "        if not N % 2:\n",
    "            return []\n",
    "        dicti = {}\n",
    "        return dfs(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    store = {0: [], 1: [TreeNode(0)]}\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N % 2 == 0:\n",
    "            return []\n",
    "        if N in self.store:\n",
    "            return self.store[N]\n",
    "        else:\n",
    "            _tmp = []\n",
    "            for left in range(N):  # left代表根节点的左子树有几个节点\n",
    "                right = N - left - 1  # right代表根节点的右子树有几个节点\n",
    "                for l in self.allPossibleFBT(left):\n",
    "                    for r in self.allPossibleFBT(right):\n",
    "                        _root = TreeNode(0)\n",
    "                        _root.left = l\n",
    "                        _root.right = r\n",
    "                        _tmp.append(_root)\n",
    "            self.store[N] = _tmp\n",
    "        return self.store[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def allPossibleFBT(self, N):\n",
    "        # 偶数无法构建满二叉树\n",
    "        if N & 1 == 0: return []\n",
    "        dp = [[] for _ in range(N+1)]\n",
    "        dp[1] = [TreeNode(0)]\n",
    "        \n",
    "        for j in range(3, N+1, 2):\n",
    "           res = []\n",
    "           for x in range(1, j, 2):\n",
    "               y = j - 1 - x\n",
    "               for left in dp[x]:\n",
    "                   for right in dp[y]:\n",
    "                       p = TreeNode(0)\n",
    "                       p.left = left\n",
    "                       p.right = right\n",
    "                       res.append(p)\n",
    "           dp[j] = res\n",
    "        return dp[N]\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    memo = {0: [], 1: [TreeNode(0)]}\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        # if N & 1 == 0:\n",
    "            # return []\n",
    "        if N not in Solution.memo:\n",
    "            ans = []\n",
    "            for x in range(N):\n",
    "                y = N - 1 - x\n",
    "                for left in self.allPossibleFBT(x):\n",
    "                    for right in self.allPossibleFBT(y):\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        ans.append(root)\n",
    "            Solution.memo[N] = ans\n",
    "        return Solution.memo[N]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    memo = {1: [TreeNode()]}\n",
    "\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N in Solution.memo:\n",
    "            return Solution.memo[N]\n",
    "        else:\n",
    "            result = []\n",
    "            for i in range(1, N, 2):\n",
    "                left_list = self.allPossibleFBT(i)\n",
    "                right_list = self.allPossibleFBT(N - 1 - i)\n",
    "                for left, right in product(left_list, right_list):\n",
    "                    if type(left) == type(right):\n",
    "                        result.append(TreeNode(0, left, right))\n",
    "            Solution.memo[N] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    memo = {i: [] for i in range(0, 21, 2)}\n",
    "    memo[1] = [TreeNode()]\n",
    "\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N in Solution.memo:\n",
    "            return Solution.memo[N]\n",
    "        else:\n",
    "            result = []\n",
    "            for i in range(1, N, 2):\n",
    "                left_list = self.allPossibleFBT(i)\n",
    "                right_list = self.allPossibleFBT(N - 1 - i)\n",
    "                for left, right in product(left_list, right_list):\n",
    "                    result.append(TreeNode(0, left, right))\n",
    "            Solution.memo[N] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N%2 == 0:\n",
    "            return []\n",
    "        index = (N-1)//2\n",
    "        def helper(irange):\n",
    "            if irange == 0:\n",
    "                return [TreeNode(0)]\n",
    "            res = []\n",
    "            ans = {}\n",
    "            for k in range(irange):\n",
    "                ans[k]=(helper(k))\n",
    "            for i in range(irange):\n",
    "                for l in ans[i]:\n",
    "                    for r in ans[irange-i-1]:\n",
    "                        tmp = TreeNode(0)\n",
    "                        tmp.left = l\n",
    "                        tmp.right = r\n",
    "                        res.append(tmp)\n",
    "            return res\n",
    "        return helper(index)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    memo = {0: [], 1:[TreeNode(0)]}\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if not N%2: return []\n",
    "        \n",
    "        if N not in Solution.memo:\n",
    "            ans = []\n",
    "            for i in range(1,N,2):\n",
    "                all_left = self.allPossibleFBT(i);\n",
    "                all_right = self.allPossibleFBT(N-1-i);\n",
    "                for l in all_left:\n",
    "                    for r in all_right:\n",
    "                        root = TreeNode(0)\n",
    "                        root.left, root.right = l, r\n",
    "                        ans.append(root)\n",
    "            Solution.memo[N] = ans\n",
    "                \n",
    "\n",
    "        return Solution.memo[N]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    memo = {0: [], 1: [TreeNode(0)]}\n",
    "\n",
    "    def allPossibleFBT(self, N):\n",
    "        if N not in Solution.memo:\n",
    "            ans = []\n",
    "            for x in range(N):\n",
    "                y = N - 1 - x\n",
    "                for left in self.allPossibleFBT(x):\n",
    "                    for right in self.allPossibleFBT(y):\n",
    "                        bns = TreeNode(0)\n",
    "                        bns.left = left\n",
    "                        bns.right = right\n",
    "                        ans.append(bns)\n",
    "            Solution.memo[N] = ans\n",
    "\n",
    "        return Solution.memo[N]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        mem = dict()\n",
    "\n",
    "        def reGetTreeList(num: int):\n",
    "            if num in mem:\n",
    "                return mem[num]\n",
    "            tree_list = []\n",
    "            # base condition\n",
    "            if num % 2 == 0:\n",
    "                mem[num] = tree_list\n",
    "                return tree_list\n",
    "            if num == 1:\n",
    "                tree_list.append(TreeNode(0))\n",
    "                mem[num] = tree_list\n",
    "                return tree_list\n",
    "            # recursive condition\n",
    "            for i in range(1, num, 2):\n",
    "                l_num = i\n",
    "                r_num = num - 1 - l_num\n",
    "                l_tree_list = reGetTreeList(l_num)\n",
    "                r_tree_list = reGetTreeList(r_num)\n",
    "                for l_root in l_tree_list:\n",
    "                    for r_root in r_tree_list:\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = l_root\n",
    "                        root.right = r_root\n",
    "                        tree_list.append(root)\n",
    "            mem[num] = tree_list\n",
    "            return tree_list\n",
    "\n",
    "        total_tree_list = reGetTreeList(N)\n",
    "\n",
    "        return total_tree_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N % 2 == 0:\n",
    "            return []\n",
    "        elif N == 1:\n",
    "            return [TreeNode(0)]\n",
    "        else:\n",
    "            result = []\n",
    "            for i in range(1, N, 2):\n",
    "                left_list = self.allPossibleFBT(i)\n",
    "                right_list = self.allPossibleFBT(N - 1 - i)\n",
    "                for left, right in product(left_list, right_list):\n",
    "                    result.append(TreeNode(0, left, right))\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        def helper(N):\n",
    "            if N == 1:\n",
    "                return [TreeNode(0)]\n",
    "            if N in memo:\n",
    "                return memo[N]\n",
    "            output = []\n",
    "            for i in range(1, N, 2):\n",
    "                for left in helper(i):\n",
    "                    for right in helper(N-1-i):\n",
    "                        new = TreeNode(0)\n",
    "                        new.left = left\n",
    "                        new.right = right\n",
    "                        output.append(new)\n",
    "            memo[N] = output\n",
    "            return output\n",
    "\n",
    "        memo = {}\n",
    "        return helper(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [TreeNode()]\n",
    "\n",
    "        self.memo = {0:None, 1:[TreeNode()]}\n",
    "        self.buildTree(n)\n",
    "        return self.memo[n]\n",
    "\n",
    "    def buildTree(self, n):\n",
    "        if n in self.memo:\n",
    "            return self.memo[n]\n",
    "        res = []\n",
    "        for i in range(1,n-1):\n",
    "            lefts = self.buildTree(i)\n",
    "            rights = self.buildTree(n-1-i)\n",
    "            for l in lefts:\n",
    "                for r in rights:\n",
    "                    node = TreeNode()\n",
    "                    node.left = l \n",
    "                    node.right = r\n",
    "                    res.append(node)\n",
    "        self.memo[n] = res[:]\n",
    "        return self.memo[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            return []\n",
    "            \n",
    "        if n == 1:\n",
    "            return [TreeNode(0)]\n",
    "\n",
    "        dp = [ [] for _ in range(n+1)]\n",
    "        #print(dp)\n",
    "        dp[1] = [TreeNode(0)]\n",
    "\n",
    "        i = 3\n",
    "\n",
    "        while i < n + 1:\n",
    "            for j in range(1, i, 2):\n",
    "                for l in dp[j]:\n",
    "                    for r in dp[i-j-1]:\n",
    "\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = l \n",
    "                        root.right = r\n",
    "                        dp[i].append(root)\n",
    "            \n",
    "            i += 2\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        @lru_cache\n",
    "        def dfs(n):\n",
    "            if n == 0:\n",
    "                return [None]\n",
    "            root = TreeNode(0)\n",
    "            if n == 1:\n",
    "                return [root] \n",
    "            ans = []\n",
    "            for l in range(1, n-1):\n",
    "                left = dfs(l)\n",
    "                right = dfs(n-l-1)\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = l \n",
    "                        root.right = r \n",
    "                        ans.append(root)\n",
    "            return ans \n",
    "        return dfs(n)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memory = {1: [TreeNode()]}\n",
    "\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        # 不存在包含偶数个节点的真二叉树\n",
    "        if n % 2 == 0:\n",
    "            return []\n",
    "        if n in self.memory:\n",
    "            return self.memory[n]\n",
    "        ans = []\n",
    "        # 遍历左子树节点个数\n",
    "        for left_num in range(1, n, 2):\n",
    "            for left in self.allPossibleFBT(left_num):\n",
    "                for right in self.allPossibleFBT(n - 1 - left_num):\n",
    "                    root = TreeNode(0, left, right)\n",
    "                    ans.append(root)\n",
    "        self.memory[n] = ans\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    memo = {0: [], 1: [TreeNode(0)]}\n",
    "\n",
    "    def allPossibleFBT(self, N):\n",
    "        if N not in Solution.memo:\n",
    "            ans = []\n",
    "            for x in range(N):\n",
    "                y = N - 1 - x\n",
    "                for left in self.allPossibleFBT(x):\n",
    "                    for right in self.allPossibleFBT(y):\n",
    "                        bns = TreeNode(0)\n",
    "                        bns.left = left\n",
    "                        bns.right = right\n",
    "                        ans.append(bns)\n",
    "            Solution.memo[N] = ans\n",
    "\n",
    "        return Solution.memo[N]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        import math\n",
    "        result=[]\n",
    "        di={}\n",
    "        # print(pow(2,2))\n",
    "        # @cache\n",
    "        def dfs(n):\n",
    "            root=TreeNode(0)\n",
    "            if n % 2 == 0:\n",
    "                return []\n",
    "            if n==1:\n",
    "                return [root]\n",
    "            if n==0:\n",
    "                return [None]\n",
    "            n-=1 \n",
    "            if n  in di:\n",
    "                return di[n]\n",
    "                \n",
    "            ln=1\n",
    "            lns=[]\n",
    "            t=[]\n",
    "            for  j in range(0,n):\n",
    "                ln=1+2*j\n",
    "                if n-ln<=0:\n",
    "                    break\n",
    "                if ln not in lns:\n",
    "                    lns.append(ln)\n",
    "                if n-ln not in lns:\n",
    "                    lns.append(n-ln)\n",
    "            # print(lns)\n",
    "\n",
    "            for ln in lns:\n",
    "                left=dfs(ln)\n",
    "                right=dfs(n-ln)  \n",
    "                # print(ln,n-ln,left,right)\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        root=TreeNode(0,left=l,right=r)\n",
    "                        t.append(root)\n",
    "\n",
    "                # if len(t)>0:\n",
    "                # print(len(t))\n",
    "            di[n]=t\n",
    "            return di[n]\n",
    "        \n",
    "        ff=dfs(n)\n",
    "        # print(di)\n",
    "        # print(ff)\n",
    "        return ff\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 1:\n",
    "            return [TreeNode(0)]\n",
    "        if n == 2:\n",
    "            return []\n",
    "\n",
    "        ans = []       \n",
    "        for i in range(1, n-1):\n",
    "            L = self.allPossibleFBT(i)\n",
    "            R = self.allPossibleFBT(n-i-1)\n",
    "            for j in L:\n",
    "                for k in R:\n",
    "                    ans.append(TreeNode(0, left=j, right=k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        memo = {0: [], 1: [TreeNode(0)]}\n",
    "        \n",
    "        def get_FBT(n):\n",
    "            if n in memo:\n",
    "                return memo[n]\n",
    "            res = []\n",
    "            for x in range(n):\n",
    "                y = n - 1 - x\n",
    "                for left in get_FBT(x):\n",
    "                    for right in get_FBT(y):\n",
    "                        p = TreeNode(0)\n",
    "                        p.left = left\n",
    "                        p.right = right\n",
    "                        res.append(p)\n",
    "            memo[n] = res\n",
    "            return res\n",
    "\n",
    "        get_FBT(N)\n",
    "        return memo[N]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        mem = defaultdict(list)\n",
    "\n",
    "        def fn(n: int, is_left=True):\n",
    "            if (n, is_left) not in mem:\n",
    "                if n == 1:\n",
    "                    mem[1, is_left] = [TreeNode(0)]\n",
    "                for i in range(1, n, 2):\n",
    "                    for left in fn(i):\n",
    "                        for right in fn(n - 1 - i, False):\n",
    "                            node = TreeNode(0)\n",
    "                            node.left = left\n",
    "                            node.right = right\n",
    "                            mem[n, is_left].append(node)\n",
    "            return mem[n, is_left]\n",
    "\n",
    "        return fn(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    @cache\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 1:\n",
    "            return [TreeNode()]\n",
    "        res = []\n",
    "        for i in range(1, n, 2):\n",
    "            for l in self.allPossibleFBT(i):\n",
    "                for r in self.allPossibleFBT(n - i - 1):\n",
    "                    root = TreeNode(0, l, r)\n",
    "                    res.append(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        if N % 2 == 0: return []\n",
    "        if N == 1:return [TreeNode(0)]\n",
    "\n",
    "        # 左子树分配x个节点, 右子数y个\n",
    "        for x in range(1,N):\n",
    "            y = N - x - 1\n",
    "\n",
    "            left = self.allPossibleFBT(x)\n",
    "            right = self.allPossibleFBT(y)     \n",
    "\n",
    "            for l in left:\n",
    "                for r in right:\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = l\n",
    "                    root.right = r\n",
    "                    ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        if N % 2 == 0: return []\n",
    "        if N == 1:return [TreeNode(0)]\n",
    "\n",
    "        # 左子树分配x个节点, 右子数y个\n",
    "        for x in range(1,N):\n",
    "            y = N - x - 1\n",
    "\n",
    "            left = self.allPossibleFBT(x)\n",
    "            right = self.allPossibleFBT(y)     \n",
    "\n",
    "            for l in left:\n",
    "                for r in right:\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = l\n",
    "                    root.right = r\n",
    "                    ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        result = []\n",
    "        if n%2 == 0:\n",
    "            return result\n",
    "        else:\n",
    "            node = TreeNode(val=0,left=None,right=None)\n",
    "            if n == 1:\n",
    "                result.append(node)\n",
    "                return result\n",
    "            else:\n",
    "                for i in range(1,n,2):\n",
    "                    left = self.allPossibleFBT(i)\n",
    "                    right = self.allPossibleFBT(n-1-i)\n",
    "                    for lnode in left:\n",
    "                        for rnode in right:\n",
    "                            node = TreeNode(val=0)\n",
    "                            node.left = lnode\n",
    "                            node.right = rnode\n",
    "                            result.append(node)\n",
    "            return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        \"\"\"\n",
    "        post-order dfs:\n",
    "        1. create a root node (n > 0)\n",
    "        2. if n > 2, left nodes number [1, n-2], right nodes [n-2, 1]\n",
    "        3. recursively call dfs, for each left tree and right tree, add to the final answer\n",
    "        \"\"\"\n",
    "        if n <= 0: return [None]\n",
    "        if n == 1: return [TreeNode()]\n",
    "\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(1, n-1, 2):\n",
    "            l_tree = self.allPossibleFBT(i)\n",
    "            r_tree = self.allPossibleFBT(n-1-i)\n",
    "            for l in l_tree:\n",
    "                for r in r_tree:\n",
    "                    ans.append(TreeNode(0, l, r))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n%2==0:\n",
    "            return []\n",
    "        dp = [[] for _ in range(n+1)]\n",
    "        dp[1].append(TreeNode())\n",
    "        for i in range(3,n+1,2):\n",
    "            for j in range(1,n-1): # [1,n-2],左侧与右侧均为奇数\n",
    "                for left in dp[j]:\n",
    "                    for right in dp[i-1-j]:\n",
    "                        root = TreeNode()\n",
    "                        # _left = copy.deepcopy(left)\n",
    "                        # _right = copy.deepcopy(right)\n",
    "                        root.left = left \n",
    "                        root.right = right \n",
    "                        dp[i].append(root)\n",
    "        print(dp[-1])\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def allPossibleFBT(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        N -= 1\n",
    "        if N == 0: return [TreeNode(0)]\n",
    "        res = []\n",
    "        for l in range(1, N, 2):\n",
    "            for left in self.allPossibleFBT(l):\n",
    "                for right in self.allPossibleFBT(N - l):\n",
    "                    node = TreeNode(0)\n",
    "                    node.left = left\n",
    "                    node.right = right\n",
    "                    res.append(node)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        dp = [[] for _ in range(n + 1)]\n",
    "        dp[1] = [TreeNode()]\n",
    "        for L in range(3, n + 1, 2):\n",
    "            for i in range(1, L, 2):\n",
    "                # print('dp[{}], dp[{}]'.format(L, i))\n",
    "                for left in dp[i]:\n",
    "                    for right in dp[L - 1 - i]:\n",
    "                        # print('left={}, right={}'.format(left, right))\n",
    "                        dp[L].append(TreeNode(0, left, right))\n",
    "            print('dp[{}]={}'.format(L, dp[L]))\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 1:\n",
    "            return [TreeNode(0)]\n",
    "\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            if i % 2 != 0:\n",
    "                left = self.allPossibleFBT(i)\n",
    "                right = self.allPossibleFBT(n-1-i)\n",
    "\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = l\n",
    "                        root.right = r\n",
    "                        res.append(root)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # 子问题：构造一棵满二叉树\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        res = []\n",
    "        if N == 1:\n",
    "            return [TreeNode(0)]\n",
    "        # 结点个数必须是奇数\n",
    "        if N % 2 == 0:\n",
    "            return []\n",
    "        \n",
    "        # 左子树分配一个节点\n",
    "        left_num = 1\n",
    "        # 右子树可以分配到 N - 1 - 1 = N - 2 个节点\n",
    "        right_num = N - 2\n",
    "        \n",
    "        while right_num > 0:\n",
    "            # 递归构造左子树\n",
    "            left_tree = self.allPossibleFBT(left_num)\n",
    "            # 递归构造右子树\n",
    "            right_tree = self.allPossibleFBT(right_num)\n",
    "            # 具体构造过程\n",
    "            for i in range(len(left_tree)):\n",
    "                for j in range(len(right_tree)):\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = left_tree[i]\n",
    "                    root.right = right_tree[j]\n",
    "                    res.append(root)\n",
    "            left_num += 2\n",
    "            right_num -= 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n % 2 == 0:\n",
    "            return []\n",
    "        res = []\n",
    "        if n == 1:\n",
    "           res. append(TreeNode()) \n",
    "        for i in range(1, n-1, 2):\n",
    "            left = self.allPossibleFBT(i)\n",
    "            right = self.allPossibleFBT(n-i-1)\n",
    "            for l in left:\n",
    "                for r in right:\n",
    "                    res.append(TreeNode(0, l, r))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        import math\n",
    "        result=[]\n",
    "        di={}\n",
    "        # print(pow(2,2))\n",
    "        # @cache\n",
    "        def dfs(n):\n",
    "            root=TreeNode(0)\n",
    "            if n % 2 == 0:\n",
    "                return []\n",
    "            if n==1:\n",
    "                return [root]\n",
    "            if n==0:\n",
    "                return [None]\n",
    "            if n  in di:\n",
    "                return di[n]\n",
    "            n-=1     \n",
    "            ln=1\n",
    "            lns=[]\n",
    "            t=[]\n",
    "            for  j in range(0,n):\n",
    "                ln=1+2*j\n",
    "                if n-ln<=0:\n",
    "                    break\n",
    "                if ln not in lns:\n",
    "                    lns.append(ln)\n",
    "                if n-ln not in lns:\n",
    "                    lns.append(n-ln)\n",
    "            # print(lns)\n",
    "\n",
    "            for ln in lns:\n",
    "                left=dfs(ln)\n",
    "                right=dfs(n-ln)  \n",
    "                # print(ln,n-ln,left,right)\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        root=TreeNode(0,left=l,right=r)\n",
    "                        t.append(root)\n",
    "\n",
    "                # if len(t)>0:\n",
    "                # print(len(t))\n",
    "            di[n]=t\n",
    "            return di[n]\n",
    "        \n",
    "        ff=dfs(n)\n",
    "        # print(di)\n",
    "        # print(ff)\n",
    "        return ff\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def M1(self, n: int) -> List[Optional[TreeNode]]:\r\n",
    "        \"\"\"\r\n",
    "        真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。\r\n",
    "\r\n",
    "        先枚举所有可能的二叉树\r\n",
    "        满二叉树：一定是奇数节点    \r\n",
    "        \"\"\"\r\n",
    "        def allFBT(n: int) -> List[TreeNode]:\r\n",
    "            if (n & 1) == 0:\r\n",
    "                return []\r\n",
    "            \r\n",
    "            if n == 1:\r\n",
    "                return [TreeNode(0)]\r\n",
    "            \r\n",
    "            trees = []\r\n",
    "            remain_node_count = n - 1 # 还可分配的节点数量， -1是为了留一个根节点\r\n",
    "            # 构造　FBT\r\n",
    "            for i in range(1, remain_node_count + 1 - 1):\r\n",
    "                left_trees: list = allFBT(i)\r\n",
    "                right_trees: list = allFBT(remain_node_count-i)\r\n",
    "                # 将左右子树拼接\r\n",
    "                for left_tree in left_trees:\r\n",
    "                    for right_tree in right_trees:\r\n",
    "                        trees.append(\r\n",
    "                            TreeNode(\r\n",
    "                                val=0,\r\n",
    "                                left=left_tree,\r\n",
    "                                right=right_tree\r\n",
    "                            )\r\n",
    "                        )\r\n",
    "            return trees\r\n",
    "        return allFBT(n)\r\n",
    "\r\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\r\n",
    "        return self.M1(n=n)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def allPossibleFBT(self, N):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        N -= 1\n",
    "        if N == 0: return [TreeNode(0)]\n",
    "        res = []\n",
    "        for l in range(1, N, 2):\n",
    "            for left in self.allPossibleFBT(l):\n",
    "                for right in self.allPossibleFBT(N - l):\n",
    "                    node = TreeNode(0)\n",
    "                    node.left = left\n",
    "                    node.right = right\n",
    "                    res.append(node)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return [TreeNode()]\n",
    "            res = []\n",
    "            for x in range(1, n, 2):\n",
    "                for left in dfs(x):\n",
    "                    for right in dfs(n-1-x):\n",
    "                        res.append(TreeNode(0, left, right))\n",
    "            return res\n",
    "                \n",
    "        return [] if n%2==0 else dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    @cache\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def dfs(n):\n",
    "            if n % 2 == 0:\n",
    "                return []\n",
    "            if n == 1:\n",
    "                return [TreeNode(0)]\n",
    "\n",
    "            res = []\n",
    "\n",
    "            for i in range(1, n - 1, 2):\n",
    "                lefts  = dfs(i)\n",
    "                rights = dfs(n - 1 - i)\n",
    "                rights = dfs(n - 1 - i)\n",
    "\n",
    "                for left in lefts:\n",
    "                    for right in rights:\n",
    "                        root = TreeNode(0)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        res.append(root)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    dict = {0:[],1:[TreeNode()]}\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        if ((n & 1) == 0):\n",
    "            return []\n",
    "        count = 3\n",
    "        while count <= n:\n",
    "            l = 1\n",
    "            Solution.dict[count] = []\n",
    "            while l <= count-2:\n",
    "                for i in Solution.dict[l]:\n",
    "                    temp1 = TreeNode()\n",
    "                    temp1.left = i\n",
    "                    for j in Solution.dict[count-l-1]: \n",
    "                        temp2 = copy.deepcopy(temp1)\n",
    "                        temp2.right = j\n",
    "                        Solution.dict[count].append(temp2)\n",
    "                l += 2 \n",
    "            count += 2\n",
    "          \n",
    "        return Solution.dict[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "      if n % 2 == 0:\n",
    "        return []\n",
    "\n",
    "      dp = [[] for _ in range(n + 1)]\n",
    "      dp[1].append(TreeNode())\n",
    "\n",
    "      \n",
    "      for i in range(3, n + 1, 2):\n",
    "        # print(f\"i = {i}\")\n",
    "        for left in range(1, n, 2):\n",
    "          right = i - left - 1\n",
    "          # print(f\"left = {left}, right = {right}\")\n",
    "          lnodes = dp[left]\n",
    "          rnodes = dp[right]\n",
    "          for l in lnodes:\n",
    "            for r in rnodes:\n",
    "              dp[i].append(TreeNode(left=l, right=r))\n",
    "\n",
    "      @cache\n",
    "      def dfs(n):\n",
    "        if n == 1:\n",
    "          return [TreeNode()]\n",
    "        res = []\n",
    "        for left in range(1, n, 2):\n",
    "          right = n - left - 1\n",
    "          lnodes = dfs(left)\n",
    "          rnodes = dfs(right)\n",
    "          for l in lnodes:\n",
    "            for r in rnodes:\n",
    "              res.append(TreeNode(left=l, right=r))\n",
    "        return res\n",
    "\n",
    "      print(dp)\n",
    "      return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, N: int) -> List[TreeNode]:\n",
    "        if N == 1:return [TreeNode(0)]\n",
    "        # 结点个数必须是奇数\n",
    "        if N % 2 == 0:return []\n",
    "        \n",
    "        res = []\n",
    "        # 左子树分配一个节点\n",
    "        left_num = 1\n",
    "        # 右子树可以分配到 N - 1 - 1 = N - 2 个节点\n",
    "        right_num = N - 2\n",
    "        while right_num > 0:\n",
    "            # 递归构造左子树、右子树\n",
    "            for left_tree in self.allPossibleFBT(left_num):\n",
    "                for right_tree in self.allPossibleFBT(right_num):\n",
    "                    root = TreeNode(0)\n",
    "                    root.left = left_tree\n",
    "                    root.right = right_tree\n",
    "                    res.append(root)\n",
    "            left_num += 2\n",
    "            right_num -= 2\n",
    "        return res     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    memo = {0: [], 1: [TreeNode(0)]}\n",
    "    def allPossibleFBT(self, n: int) -> List[TreeNode]:\n",
    "        \n",
    "        if n == 1:\n",
    "            return [TreeNode(0)]\n",
    "        ans = []\n",
    "        for left in range(1, n, 2):\n",
    "            right = n - left - 1\n",
    "\n",
    "            left_list = self.allPossibleFBT(left)\n",
    "            right_list = self.allPossibleFBT(right)\n",
    "            for left_tree in left_list:\n",
    "                for right_tree in right_list:\n",
    "                    temp = TreeNode(0)\n",
    "                    temp.left = left_tree\n",
    "                    temp.right = right_tree\n",
    "                    ans.append(temp)\n",
    "        Solution.memo[n] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) :\n",
    "        if n % 2 == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [TreeNode(0)]\n",
    "        output = []\n",
    "        for i in range(1,n,2):\n",
    "            for w in self.allPossibleFBT(i):\n",
    "                for m in self.allPossibleFBT(n - 1 - i):\n",
    "                    output.append(TreeNode(0,w,m))\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n==1:\n",
    "            return [TreeNode(0)]\n",
    "        ans=[]\n",
    "        for i in range(1,n-1):\n",
    "            for x in self.allPossibleFBT(i):\n",
    "                for y in self.allPossibleFBT(n-1-i):\n",
    "                    ans.append(TreeNode(0,x,y))\n",
    "        return ans \n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
